1. Field of the Invention
The present invention relates to a configuration of a two-dimensional code and to a method and an apparatus for detecting a two-dimensional code from an image.
2. Description of the Related Art
[Related Art 1]
A known two-dimensional code called MaxiCode is shown in FIG. 18. In this two-dimensional code, tiny regular hexagonal cells are regularly arranged around concentric ring-like black and white regions having different radii which are positioned at a center part of the two-dimensional code. Each of the regular hexagonal cells is colored black or white, thereby representing binary information. The content of the code is read out by capturing an image of the code using a camera or the like. This type of two-dimensional code will hereinafter be referred to as “two-dimensional code 1”.
Two-dimensional codes shown in FIGS. 19 and 20 are also known. Each of these two-dimensional codes has a square exterior region which can be distinguished from the background on the basis of the brightness, and small square cells formed by dividing an interior region of the code into equally sized regions. Information is expressed by the brightness/darkness of the small square cells. Normally, an image of such a two-dimensional code is captured by a camera, and the perimeter (contour) or external shape of the code is identified and detected from the captured image. Information represented by the code is read out on the basis of the brightness of each of the small square cells allocated within the detected perimeter (contour). This type of two-dimensional code will hereinafter be referred to as “two-dimensional code 2”.
In general, “two-dimensional code 1” and “two-dimensional code 2” are to be attached to an article or the like and used to manage information such as manufacturing information including the product number, product ID, and manufacturing date, and transportation information including the origin, destination, and transportation date/time. Reading of such a two-dimensional code is performed on the premise that the image of the code is captured by a camera from a position generally right in front of the code (i.e., a position at which the optical axis of the camera is generally exactly perpendicular to the code) and that the captured code image is sufficiently large.
[Related Art 2]
In the field of mixed reality (MR), in which a virtual object is superimposed on a real space so as to be displayed in the real space, the following processing is performed to render a virtual image. The position and orientation of a real camera with respect to a square marker disposed in the real space are estimated. On the basis of the estimated position and orientation of the real camera, parameters of the virtual camera are set. Then, a virtual image is rendered on the basis of the set parameters.
An example of a technique used in such MR applications is ARToolkit, which is described in X. Zhang, S. Fronz, N. Navab: “Visualmarker detection and decoding in AR systems: A comparative study,” Proc. of International Symposium on Mixed and Augmented Reality (ISMAR'02), 2002 (hereinafter referred to as “Zhang et al.”). In ARToolkit, a marker having a square perimeter (contour) or external shape as shown in FIG. 21 is used. A quadrangular shape of the marker perimeter (contour) is detected from a captured image. Then, a position and orientation of a camera are estimated on the basis of how the detected quadrangular shape is deformed from the original square shape (i.e., the detected quadrangle is distorted by the effect of perspective projection). Further, in order to distinguish a marker from a plurality of markers, the interiors of the individual markers are applied with different patterns. Each of the markers is distinguished by performing processing called pattern matching on the pattern inside the quadrangle obtained from the captured image. This type of two-dimensional code will hereinafter be referred to as “two-dimensional code 3”.
Another example of a marker used in MR applications is shown in FIG. 22, which is described in “Zhang et al.”. This marker is different from “two-dimensional code 3” in that the interior of the marker is divided into a 4×4 grid pattern. In addition, a function of distinguishing each marker is realized on the basis of whether or not each of the circular regions, with its center at the center of one of the divided grid cells, is black. However, this marker is the same as “two-dimensional code 3”, in that the position and orientation of a camera are estimated on the basis of the original square contour. This type of two-dimensional code will hereinafter be referred to as “two-dimensional code 4”.
Other types of marker having square contours have been proposed in the field of MR. For example, a marker shown in FIG. 23 has a plurality of small square cells disposed outside its square contour. These small square cells are used to identify a rotation direction of the square contour within a captured image. The interior of the marker is divided into 4×4 square cells. Information for distinguishing the marker is represented by the brightness of each of the small square cells. This type of two-dimensional code will hereinafter be referred to as “two-dimensional code 5”.
A feature common to the above-described “two-dimensional code 3”, “two-dimensional code 4”, and “two-dimensional code” for MR applications is that all they have a square contour.
“Two-dimensional code 1” described in “Related Art 1” has concentric circles disposed at the center of the code which are surrounded by small regular hexagonal cells. These regular hexagonal cells are interlocked with each other, and each is colored either black or white. These black and white cells represent binary data. The positions of the hexagonal cells are identified using lines as references which radiate from the innermost concentric circle at 60 degree intervals. In other words, only when the image of “two-dimensional code 1” is captured from a position generally right in front of the code (index) (i.e., when the image is captured using a camera having an optical axis generally along a normal to the plane to which the index is attached), can the index be detected. This is true for “two-dimensional code 2”. Capturing of images of the two-dimensional codes of Related Art 1 described above is performed on the premise that images of the indices are captured from a position at which the optical axis of the camera is generally exactly perpendicular to the plane of the indices, and it is not intended for images to be captured from an arbitrary position at which the optical axis of the camera is not exactly perpendicular to the plane of the indices.
Every one of “two-dimensional code 3”, “two-dimensional code 4”, and “two-dimensional code 5” described above has an exterior region having a square contour. The brightness of this region is lower than that of the background. In a technique of Related Art 2, estimation calculation is performed for determining the position and orientation of a camera with respect to a two-dimensional code, on the basis of deformation of the contour of the code. The deformation occurs due to the projection of a three-dimensional feature onto a two-dimensional plane. That is, capturing of images of the indices of Related Art 2 is not performed on the premise that their images are captured from a direction exactly perpendicular to the plane of the indices. Rather, capturing of image of these indices is performed on the premise that the images are captured from a direction that possibly deviates from the direction normal to the plane of the indices.
For “two-dimensional code 3”, in order to distinguish individual indices, arbitrary patterns in the interior of the square contours are identified through a pattern matching technique. Patterns in the interiors of the indices are independently stored in advance for use in pattern matching. Then, after an image obtained by clipping the interior region of the index out of a captured image is normalized, the normalized image and a stored pattern are compared so that the index is identified on the basis of whether or not the normalized image resembles the stored pattern. This technique, however, has a disadvantage in that the number of pairs to be pattern-matched increases as the number of patterns to be used or indices to be image-captured at the same time increases. This may result in a significant increase in the time necessary for calculations. In addition, an increase in the number of patterns produces similar patterns, causing possible misrecognition of the patterns. Thus, not more than approximately several tens of patterns can actually be used at the same time.
On the other hand, in “two-dimensional code 4” and “two-dimensional code 3”, the interior region is equally divided into small square cells, and a bit value is represented by the brightness (black or white) of each cell. Thus, “two-dimensional code 4” and “two-dimensional code 5” are free from the disadvantage associated with “two-dimensional code 3” described above. However, “two-dimensional code 4” and “two-dimensional code 5” still have a room for improvement as described below.
In order for a two-dimensional code to contain as much information as possible, it is necessary to increase the number of bit cells. However, since individual bit cells have to be recognized from a captured image, there is a limitation in decreasing the size of each bit cell. In other words, the recognizability of the two-dimensional code depends on the size of a bit cell captured/projected on an image. In general, a smaller two-dimensional code is desirable for MR applications. However, when amount of information to be recorded in the two-dimensional code is increased, the size of the two-dimensional code has to be physically increased so that it appears sufficiently large in the captured image. That is, the size of a two-dimensional code and the amount of information contained therein are in a trade-off relationship. Thus, in order to decrease the size of the two-dimensional code and also to record as much information as possible, it is desired to arrange bit cells with high density in the interior region of the code.
“Two-dimensional code 4” has circular interior bit cells arranged in square grid. With this type of two-dimensional code, the size of spaces between the circular cells becomes important when the size of each circular bit cell is decreased. For example, when the size a circular bit cell colored black is decreased to the size of the width of a pixel in a captured image, the cell will appear to be mixed with white space around the cell, creating a region of neutral brightness. This results in an increase in the number of errors in bit readout. That is, it is desirable that the interior cells are arranged close together without spaces therebetween.
In “two-dimensional code 5”, the interior region is equally divided into square bit cells which are adjacent to each other. Thus, this type of two-dimensional code is free from the above problem associated with “two-dimensional code 4”. In addition, the marker can be detected even when the image within which it appears is captured from a direction which is not exactly perpendicular to the plane of the marker. Thus, it is not definite from which direction the image of interior small square cells will be captured. That is, it is indefinite what types of quadrangular shape of these cells will appear in a projected image. In “two-dimensional code 5”, processing for converting the code into a bit-based representation is performed on the basis of the brightness of the individual square cells in a captured image. Thus, when the brightness is read, the brightness of the center point of each square cell (brightness reference point) is to be read out. In order to accurately read the brightness, it is necessary to capture the image of the code so that there is a sufficient constant distance between the brightness reference points of the square cells in the captured image. In other words, when the image of the cells in the original index is projected onto an image plane, the closer to a circular shape, with its center at the brightness reference point, each cell in the projected image appears in the image plane, the more the size of the cells in the original index can be decreased. The number of bits to be allocated for the entire index area can be increased by decreasing the size of the cells, each cell representing a bit value. In contrast, when the cells are in the shape of a square, indicating each cell appears quadrangular with corners in the image plane, these cells may not be arranged efficiently with high density.
On the other hand, in “two-dimensional code 4”, individual bit cells are circular. However, there are unnecessary spaces between the cells, and thus these cells may not be arranged with high density.